#include "stack_queue.h"
using namespace std;

void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}




// MyStack implementation
MyStack::MyStack() : topNode(nullptr), stackSize(0) {}

MyStack::~MyStack() {
    while (topNode) {
        listNode* temp = topNode;
        topNode = topNode->next;
        delete temp;
    }
}

bool MyStack::push(const int& value) {
    listNode* newNode = new listNode(value, topNode);
    topNode = newNode;
    stackSize++;
    return true;
}

bool MyStack::pop(int& item) {
    if (!topNode) return false; // Stack is empty
    item = topNode->data;
    listNode* temp = topNode;
    topNode = topNode->next;
    delete temp;
    stackSize--;
    return true;
}

bool MyStack::getTop(int& item) {
    if (!topNode) return false; // Stack is empty
    item = topNode->data;
    return true;
}


// MyQueue implementation
MyQueue::MyQueue(const int& cap) : capacity(cap), front(0), rear(0) {
    queue = new int[capacity];
}

MyQueue::~MyQueue() {
    delete[] queue;
}

bool MyQueue::enQueue(const int& value) {
    if (isFull()) return false; // Queue is full
    queue[rear] = value;
    rear = (rear + 1) % capacity;
    return true;
}

bool MyQueue::deQueue(int& item) {
    if (front == rear) return false; // Queue is empty
    item = queue[front];
    front = (front + 1) % capacity;
    return true;
}

bool MyQueue::getFront(int& item) {
    if (front == rear) return false; // Queue is empty
    item = queue[front];
    return true;
}

bool MyQueue::isFull() {
    return (rear + 1) % capacity == front; // Queue is full
}

bool postfixExpression(const std::string& infix, std::string& result) {
    std::stack<char> opStack;
    result.clear();
    std::vector<char> output;

    for (char ch : infix) {
        if (isdigit(ch)) {
            output.push_back(ch);
        } else if (ch == '(') {
            opStack.push(ch);
        } else if (ch == ')') {
            while (!opStack.empty() && opStack.top() != '(') {
                output.push_back(opStack.top());
                opStack.pop();
            }
            if (opStack.empty()) {
                result = "Expression is wrong!";
                return false;
            }
            opStack.pop(); // Remove '('
        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            while (!opStack.empty() && opStack.top() != '(' &&
                   ((ch == '+' || ch == '-') || (opStack.top() == '*' || opStack.top() == '/'))) {
                output.push_back(opStack.top());
                opStack.pop();
            }
            opStack.push(ch);
        } else {
            result = "Expression is wrong!";
            return false;
        }
    }

    while (!opStack.empty()) {
        if (opStack.top() == '(') {
            result = "Expression is wrong!";
            return false;
        }
        output.push_back(opStack.top());
        opStack.pop();
    }

    result = std::string(output.begin(), output.end());
    return true;
}


// Expression evaluation
bool expressionVal(const string& expression, int& result) // 表达式求值
{
    string postfix;
    if (!postfixExpression(expression, postfix)) //所给的表达式不能转化为后缀表达式
    {
        result = 0;
        return false;
    }

    MyStack evalStack;
    for (char c : postfix) 
    {
        if (isdigit(c)) 
        {
            evalStack.push(c - '0'); //数字入栈
        } 
        else // 运算符
        { 
            int rightOperand, leftOperand;
            evalStack.pop(rightOperand);
            evalStack.pop(leftOperand);//弹出两个数
            int res = 0; //储存两个数的运算结果

            switch (c) 
            {
                case '+': res = leftOperand + rightOperand; break;
                case '-': res = leftOperand - rightOperand; break;
                case '*': res = leftOperand * rightOperand; break;
                case '/':
                    if (rightOperand == 0) // 除以零
                    {
                        result = 0;
                        return false; 
                    }
                    res = leftOperand / rightOperand; 
                    break;
                
                default:
                    result = 0;
                    return false; 
                    
            }
            evalStack.push(res); // 将结果放入栈中
        }
    }

    if (!evalStack.getTop(result)) //无法取出运算结果
    { 
        result = 0;
        return false; 
    }
    return true;
}


// Yanghui triangle output
void yanghui(const int& n)  //杨辉三角
{  
    MyQueue q(n + 3);  
    //队列初始化
    //通过观察可以发现第一行需要三个位置，
    //第二行需要四个位置，
    //以此类推，第n行需要n+2个位置（n+1个数据，1个辅助运算的0）
    //又因为队列不插满，需要留出一个位置，所以n+3

    q.enQueue(1);  
    q.enQueue(1);
    int s=0;
    //逐行处理，输出第一行参数的同时计算第二行参数并入栈
    //（0） 1 1 0
    for (int i = 1; i <=n; ++i)  
    {  
        q.enQueue(0); 
  
        for (int j = 1; j <=i+2; ++j)  
        {  
            int t;
            q.deQueue(t);
            q.enQueue(s+t);
            s=t;
            if(j!=i+2)
            {
                if(j!=i+1)
                {
                    cout<<s<<",";//非本行最后一个输出数时，后面带一个逗号
                }
                else
                {
                    cout<<s;
                }
            }
        } 
        cout<<endl;  
    }  
}